/**
 * 64. 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/
 */

/**
 * @param {number[][]} grid
 * @return {number}
 */
function minPathSum(grid) {
  const { length: n } = grid;
  const { length: m } = grid[0];
  for (let j = 1; j < m; j += 1) {
    grid[0][j] = grid[0][j - 1] + grid[0][j];
  }
  for (let i = 1; i < n; i += 1) {
    grid[i][0] = grid[i - 1][0] + grid[i][0];
  }
  for (let i = 1; i < n; i += 1) {
    for (let j = 1; j < m; j += 1) {
      grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
    }
  }
  return grid[n - 1][m - 1];
}

console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) === 7);
console.log(minPathSum([[1, 2, 3], [4, 5, 6]]) === 12);
